package 剑指offer.demo1;//https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?%20tpId=13&tqId=11154&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-%20interviews/question-ranking

/**
 * 题目思路：一行一行做判断，每次先判断当前行最右面即是那个元素所属列最小的，如果查找值target大于它，让行号递增查找即可；如果target小于它，让列号递减继续做判断
 * 1、查找过程本质是排除过程，排除效率高，查找效率高比如二分查找每次排除一半
 */
public class 二维数组的查找 {
    public boolean Find(int target, int [][] array) {
        //判空
        if (array == null){
            return false;
        }
        //定义行列；因为列的第一个元素是当前列最小的，行的最右面是当前行最大的
        int i = 0;//行
        int j = array[0].length - 1;//列，右上角（第一行最最大值，最后一列最小值）
        while (i < array.length && j >= 0){
            //还在范围内，行没超标，列也没超标
            if (target < array[i][j]){
                j -- ;
            }else if (target > array[i][j]){
                i ++ ;
            }else {
                //当前值相等即找到了
                return true;
            }
        }
        //跳出循环时，查找完了所有元素，说明没找到
        return false;
    }
}
